package class5;

import common.TreeNode;
import common.TreeNodeUtils;

/**
 * 求二叉树的最大距离
 */
public class Code13_MaxDistance {

    public static void main(String[] args) {
        TreeNode noBalanceTree = TreeNodeUtils.getNoBalanceTree();
        int maxDistance = maxDistance(noBalanceTree);
        System.out.println("maxDistance = " + maxDistance);
    }

    public static int maxDistance(TreeNode treeNode) {
        return process(treeNode).maxDistance;
    }

    public static Info process(TreeNode treeNode) {
        if (treeNode == null) {
            return new Info(0, 0);
        }

        Info left = process(treeNode.left);
        Info right = process(treeNode.right);
        // 当前节点高度
        int high = Math.max(left.high, right.high) + 1;
        // 最大距离
        /**
         * 1.左右子树的最大距离
         * 2.左右子树的最大高度+1
         * 比较
         * 3.将更大的值存到maxDistance
         */
        int maxDistance = Math.max(
                Math.max(left.maxDistance, right.maxDistance), (left.high + right.high + 1));
        return new Info(high, maxDistance);
    }


    static class Info {
        public int high;
        public int maxDistance;

        public Info(int high, int maxDistance) {
            this.high = high;
            this.maxDistance = maxDistance;
        }
    }
}
